This invention relates to methods and a system for secure communication between an RFID tag and a reader via the over-the-air interface, and to corresponding RFID tags and corresponding readers.
RFID technology (“radio frequency identification”) enables in particular the automatic identification of persons and objects, and is becoming increasingly widespread in a multiplicity of applications, such as for example in supply chain management, in access control systems, in systems for theft protection of goods, in electronic ticketing, and the like. An RFID system normally consists of a portable data carrier in the form of an RFID tag (also called a transponder), which a person carries or is attached to an object and which stores an identification code uniquely identifying the RFID tag and/or the object (also known to the person skilled in the art as a Unique ID (UID), Tag-ID (TID) or “Unique Item Identifier” (UII)), and a reader for contactlessly reading out the identification code of the RFID tag. The reader is usually only one reader of a multiplicity of readers which are installed at different locations and can access, via a background system, data deposited there for a multiplicity of RFID tags.
In particular those inexpensive RFID tags intended for logistics applications and for supply chain management, which are normally passive RFID tags that draw the energy required for operation from the electromagnetic field of a reader, frequently offer no cryptographic functions, so that an authentication of an RFID tag to a reader is not possible with such RFID tags. This is the case for example with UHF RFID tags, which are known to the person skilled in the art under the name Class-1 Gen-2 EPC tags, i.e. RFID tags that are configured according to the standard EPC Class 1 Generation 2 or the newer standard ISO/IEC 18000-63. As is known to the person skilled in the art, the term “Class-1 Gen-2 EPC tags” also includes tags according to the standard ISO/IEC 18000-63. In such RFID tags the unique identification code is referred to as the EPC (“Electronic Product Code”), which is usually a bit sequence consisting of 96 bits and deposited in a respective RFID tag. Upon a readout of an RFID tag the EPC is transferred to a reader in plaintext without authentication and can thus be intercepted both actively, by a reader of an unauthorized third party, and passively, by a third party monitoring the insecure communication channel, i.e. the over-the-air interface, between the RFID tag and a reader.
This leads to two potential problems, namely, firstly, that the presence and the position of an RFID tag can be detected and tracked by an unauthorized third party, which is also referred to as tracking of an RFID tag, and, secondly, that a third party can copy the read-out EPC into a new, forged RFID tag and can thus pass off the new, forged RFID tag as the tag from which the EPC was originally read out, which is also referred to as cloning an RFID tag.
For securing the communication between an RFID tag and a reader it is expedient to use cryptographic methods which enable, firstly, a unilateral or mutual authentication between the RFID tag and the reader and, secondly, an encryption of the communication via the over-the-air interface. Cryptographic methods are subdivided into symmetric methods, in which transmitter and receiver employ the same secret key, and public-key or asymmetric methods, in which the transmitter employs a public key and the receiver a secret or private key. However, symmetric methods are known to involve the problem that the common secret key must be deposited securely both in an RFID tag and in a reader or a background system connected thereto, which requires an elaborate key management in systems with a multiplicity of RFID tags and a multiplicity of readers, this being unnecessary in public-key or asymmetric methods. Such a key management can also be omitted in systems employing a symmetric method if the same master key is deposited in all RFID tags and in the background system. However, this involves the danger that as soon as the master key of an RFID tag has been established the whole system is broken. This danger does not exist in public-key methods.
A known public-key method is the Rabin method which, like the frequently used RSA method, utilizes modular exponentiation as its basis. Since the computation of the encryption is substantially simpler, i.e. less compute-intensive, in the Rabin method than in the RSA method, the Rabin method is preferable to the RSA method in particular where the entity carrying out the encryption, i.e. the transmitter of an encrypted message, has only limited processor power, as is the case for example with a limited-resource RFID tag that is to communicate securely with a reader coupled to a background system.
In the Rabin method the secret key consists of two prime numbers p and q, chosen in practice to be sufficiently large, which are linked with each other via a certain congruence condition. The product n=p·q of the two prime numbers p and q defines the modulus n and simultaneously represents the public key. Expediently, the prime numbers p and q are approximately equally large. According to the Rabin method, a plaintext M to be transmitted is encrypted by modular squaring and applying the modulo operation, i.e. the ciphertext C results from the plaintext M according to the following formula: C=M2 mod n.
The security of the Rabin method is based on the fact that it is very difficult to compute the modular square root from the ciphertext C without knowing the prime numbers p and q. However, this is only the case when the plaintext M is not substantially smaller than the modulus n. The modulo operation following squaring prevents the possibility of decryption by simply taking the root.
Since in the Rabin method the encryption by the transmitter involves a modular squaring, the receiver must for decryption compute the modular square root of the ciphertext C. As is known, this can be done utilizing the Chinese remainder theorem (CRT). As the person skilled in the art knows, this results in four square roots from which one must be selected as the original plaintext M. For this purpose, the “right” plaintext M can be marked for the receiver for example by means of a suitable identifier, check sum or the like.
As results from the hereinabove described formula for computing the ciphertext C in the Rabin method, the transmitter must normally carry out an arbitrary-precision division to carry out the modulo operation. However, such an arbitrary-precision division can only be realized very elaborately in particular on simple microprocessors as are employed with RFID tags.
The publication “A Low-Resource Public-Key Identification Scheme for RFID Tags and Sensor Nodes” by Y. Oren and M. Feldhofer in D. A. Basin, S. Capkun, and W. Lee, editors, WISEC, pages 59-68, ACM 2009, proposes under the name of WIPR method a modification of the conventional Rabin method which is intended in particular for securing the communication between a limited-resource RFID tag with a simple processor and a reader. Compared with the hereinabove described conventional Rabin method, the WIPR method has the advantage of employing for computing the ciphertext, instead of an elaborate arbitrary-precision division which is very compute-intensive and can thus hardly be implemented on simple microprocessors as are usually found on RFID tags, arbitrary-precision multiplications, which are substantially faster to execute than divisions and can also be realized more simply in terms of hardware.
According to the WIPR method, the ciphertext C′ is computed by the transmitter, e.g. an RFID tag, generating a random number r, multiplying it by the modulus n and adding the result to the square of the plaintext M, i.e. C′=M2+r·n. In so doing, an identification code of the RFID tag is incorporated into the plaintext M and the size of the random number r is so chosen that the product r·n is more than twice as large as the modulus n. In contrast to the conventional Rabin method, the square of the plaintext M is thus not masked in the WIPR method by carrying out the modulo operation which involves an arbitrary-precision division, but by adding the product r·n with the suitably chosen random number r.
The publication A. Shamir, “Memory Efficient Variants of Public-Key Schemes for Smart Card Applications”, in A. D. Santis, editor, Advances in Cryptology—EUROCRYPT'94, Springer LNCS, Vol. 950, pages 445-449, has shown that a method like the WIPR method is just as secure as the conventional Rabin method provided the random number r is chosen randomly from a sufficiently large number range.
However, the price paid by the WIPR method for the advantage of avoiding an arbitrary-precision division is that the ciphertext C′ will normally be very long due to the omission of the modulo operation when squaring the plaintext M and due to the product of the modulus n with the sufficiently large random number r, which slows down the authentication operation between an RFID tag and a reader since a larger amount of data must be transferred from the RFID tag to the reader.